Networks have become complex and more versatile in recent years. As a result, there are demands to quickly and accurately locate an abnormality in the network in network monitoring, fault monitoring and the like.
Conventionally, as one example of a technique to locate the abnormality in the network, there is a network tomography analysis that analyzes the abnormality within the network based on normal or abnormal information of an end-to-end observation flow (or measurement flow) of the network. Such a network tomography analysis is proposed in Atsuo Tachibana et al., “Empirical Study on Locating Congested Segments over the Internet Based on Multiple End-to-End Path Measurements”, Technical Report of IEICE, The Institute of Electronics, Information and Communication Engineers, CQ2004-76, OIS2004-30, IE2004-37 (CQ Vol. 104, No. 309), September 2004, pp. 43-48, for example. The observation flow refers to a route that is specified by a source observation point and an end observation point and is used to monitor the abnormality based on quality information such as a packet loss rate.
A description will now be given of the example of the network tomography analysis, by referring to FIGS. 1 and 2. FIG. 1 is a diagram illustrating an example of a network in which an abnormality is to be located. FIG. 2 is a matrix diagram illustrating examples of observation flows mapped with observation flow passing links through which the observation flows that observe an abnormality pass. FIG. 2 illustrates the matrix diagram in a state after elimination of observation flow passing links through which the observation flows that observe normality pass.
The network illustrated in FIG. 1 includes flow quality measuring agents A through E, relay nodes R1 through R6, and links 1 through 12. It is assumed for the sake of convenience that the links 2 and 5 are abnormality generated links in which an abnormality, such as packet loss, is generated. In FIG. 1, the observation flow is represented by a sign of the flow quality measuring agent at a source and a sign of the flow quality measuring agent at a destination. For example, an observation flow of the source flow quality measuring agent A and the destination flow quality measuring agent B is represented by AB.
For example, the network tomography analysis generally includes procedures p1, p2 and p3. The procedure p1 judges whether each observation flow is normal or abnormal, and maps normal or abnormal information to the observation flow passing link through which the observation flow passes. The procedure p2 eliminates the normal flow passing link through which one or more normal observation flows pass. The procedure p3 judges a link set covering the abnormal observation flow in which the abnormality is observed as a suspicious location of the abnormality.
In the case of the matrix diagram illustrated in FIG. 2, all of the abnormal observation flows may be covered by one of the link sets of the links 2 and 5, the links 2 and 3, and the links 3 and 5 or, by the link set of the links 2, 3 and 5. Hence, the link sets of the links 2 and 5, the links 2 and 3, the links 3 and 5, and the links 2, 3 and 5 are regarded as the suspicious locations of the abnormality.
However, if the procedure p3 of the network tomography analysis may obtain a plurality of link sets covering the abnormal observation flows, a correct diagnosis cannot be obtained in a case where a suspicious location of the abnormality is erroneously located (that is, an erroneous detection), and in a case where an abnormal location is erroneously judged as being normal (that is, an abnormality overlook).
In addition, in the process of extracting the link set covering the abnormal observation flows, it is necessary to solve the algorithm of a set cover problem. For this reason, even if an approximation algorithm is used, the processing load (or processing time) of the process of extracting the link set covering the abnormal observation flows becomes large, and the judgement to determine whether a plurality of link sets may be obtained is not carried out in some cases. In such cases, it is impossible to judge the accuracy of the diagnosis result.
Therefore, according to the conventional network tomography analysis, the accuracy of the diagnosis result may deteriorate because the diagnosis result may include the erroneous detection or the abnormality overlook, depending on the pattern of the locations where the abnormality is generated. Moreover, the conventional network tomography analysis cannot judge the accuracy of the diagnosis result from the pattern of the locations where the abnormality is generated.